import java.util.*

class AbstractSort {
    fun insertSort(array: IntArray) {
        for (index in 1 until array.size) {
            val temp = array[index]
            var left = index - 1
            while (left >= 0 && array[left] < temp) {
                array[left + 1] = array[left]
                left--
            }
            array[left + 1] = temp
            println(array.contentToString())
        }
    }

    fun shellSort(array: IntArray) {
        var step: Int = array.size / 2
        while (step > 0) {
            //对一个步长区间进行比较 [step,arr.length)
            println("step=$step")
            for (i in step until array.size) {
                val value: Int = array[i]
                //对步长区间中具体的元素进行比较
                var j: Int = i - step
                while (j >= 0 && array[j] > value) {
                    //j为左区间的取值，j+step为右区间与左区间的对应值。
                    array[j + step] = array[j]
                    j -= step
                }
                //此时step为一个负数，[j + step]为左区间上的初始交换值
                array[j + step] = value
            }
            step /= 2

        }
    }

    fun quickSort(array: IntArray, left: Int, right: Int) {
        if (left < right) {
            var i = left
            var j = right
            val pivot = array[left]
            while (i < j) {
                while (i < j && array[j] >= pivot) {
                    j--
                }
                if (i < j) {
                    array[i] = array[j]
                    i++
                }
                while (i < j && array[i] < pivot) {
                    i++
                }
                if (i < j) {
                    array[j] = array[i]
                    j--
                }
            }
            array[i] = pivot
            quickSort(array, left, i - 1)
            quickSort(array, i + 1, right)
        }
    }

    //三向切分快排
    fun dualQuickSort(array: IntArray, left: Int, right: Int) {
        if (left >= right) return
        var i = left
        var it = i + 1
        var j = right
        val pivot = array[i]
        while (i <= j) {
            when{
                array[i] < pivot ->{
                    val temp = array[it++]
                    array[it] = array[i++]
                    array[i] = temp
                }
                array[i] < pivot ->{
                    val temp = array[i]
                    array[i] = array[j--]
                    array[j] = temp
                }
                else-> {
                    i++
                }
            }
        }
        dualQuickSort(array,left,it-1)
        dualQuickSort(array,j+1,right)
    }

    fun heapSort(){
        //TODO
    }

    fun mergeSort(){
        //TODO
    }
}


fun main() {
    val array = arrayOf(1, 2, 3, 5, 2, 7, 8, 3, 11, 62, 22, 8, -1, 0)
    val arr = array.toIntArray()
    val insert = AbstractSort()
    insert.dualQuickSort(arr, 0, arr.size - 1)
    Arrays.sort(arr)
    println("res=${arr.contentToString()}")
}